package org.example.leetcode;
import java.util.LinkedHashMap;
import java.util.Map;
/**
 * @version 1.0.0
 * @author: lynn
 * @description:整数转罗马数字
 * @date: 2021/7/25 9:01
 */
public class LC12 {
    public static void main(String[] args) {
        LC12  lc=new LC12();
        System.out.println(lc.intToRoman(27));
    }
    /**
     小结：
     1. 卡的地方在于动态规划？no
     2. map的遍历，根据key的类型遍历
     3. 不同于找零钱，可以跳着来，就是说1800，你只能是1000+500+100+100+100，不能 900+900 ，如果是找零钱可以用动态规划
     */
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    public String intToRoman(int num) {
        String res="";
        Map<String,Integer> romansMap=new LinkedHashMap<>();
        while (num>0) {
            for (int i = 0; i <values.length ; i++) {
                if (num<values[i]) continue;
                int count=num/values[i];
                num=num%values[i];
                romansMap.put(symbols[i],count);
            }
        }
        //fixme 难点在于map的遍历
        for (String key:romansMap.keySet()){
            int count=romansMap.get(key);
            while (count>0){
                count--;
                res=res+key;
            }
        }
        return res;
    }
}
